package practice;

import java.util.Scanner;

public class _16Boom {
    static int t;
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        t = scanner.nextInt();
        while (t-- > 0){
            int n,m,k;
            n = scanner.nextInt();
            m = scanner.nextInt();
            k = scanner.nextInt();

            //int[][] grid = new int[n][m];
            //  轮流炸 x+y 为奇数或者偶数的点
            if(n*m == 1){
                System.out.println(k);
            }else {
                long f1 = (long) n * m / 2, f2 = (long) n * m - f1;
                long k1 = (k + 1) / 2, k2 = k + 1 - k1;
                System.out.println(Math.min(f1 * k1 + f2 * k2, f1 * k2 + f2 * k1));
            }
        }
    }
}
